package com.yunsom.testdemo.leetcode.sort;

public class QueryAlgorithmPratice {
    public static void main(String[] args){
        int [] arr = new int[]{1,3,5,6,8,9,77,646,2044,4666,7444,23444,29345};
        System.out.println(dichotomyQueryByRecursive(arr, 0, 12,0));
        System.out.println(dichotomyQueryByRecursive(arr, 0, 12,1));
        System.out.println(dichotomyQueryByRecursive(arr, 0, 12,7444));
        System.out.println(dichotomyQueryByRecursive(arr, 0, 12,29345));
    }

    //二分查找某集合中的一个元素的下标，如果没有查到结果，返回-1
    /*
    循环实现
     */
    public static int dichotomyQuery(int[] arr, int value){
        int index = -1;
        int start = 0;
        int end = arr.length - 1;
        int mid;

        while (end >= start){
            mid = (start + end)/2;
            if(arr[mid] < value){
                start = mid + 1;
            } else if(arr[mid] > value){
                end = mid -1;
            } else {
                index =  mid;
                break;
            }
        }

        return index;
    }
    /*
    递归实现
     */
    public static int dichotomyQueryByRecursive(int[] arr, int start, int end, int value){
        if(start > end){
            return -1;
        }
        int mid = (start + end)/2;
        if(arr[mid] == value){
            return mid;
        } else if(arr[mid] < value){
            start = mid + 1;
            return dichotomyQueryByRecursive(arr, start, end, value);
        } else {
            end = mid -1;
            return dichotomyQueryByRecursive(arr, start, end, value);
        }
    }
}
